import java.util.*;

public class Main {


    /**
     * 反转链表
     */
      public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
     }

    public static ListNode ReverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while(head != null) {
            stack.push(head);
            head = head.next;
        }
        if(stack.empty()) {
            return null;
        }
        ListNode node = stack.pop();
        ListNode newHead = node;
        while(!stack.empty()) {
            ListNode tmp = stack.pop();
            node.next = tmp;
            node = node.next;
        }
        node.next = null;
        return newHead;
    }
    public static ListNode ReverseList2(ListNode head) {
          ListNode newHead = null;
          while(head != null) {
              ListNode tmp = head.next;
              head.next = newHead;
              newHead = head;
              head = tmp;
          }
          return newHead;
    }

    /**
     * 链表内指定区间反转
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        for(int i = 0; i < m-1; i++) {
            pre = pre.next;
        }
        ListNode rightNode = pre;
        for(int i = 0; i < n - m + 1; i++) {
            rightNode = rightNode.next;

        }

        ListNode leftNode = pre.next;
        ListNode cur = rightNode.next;

        rightNode.next = null;
        pre.next = null;

        ReverseList(leftNode);

        pre.next = rightNode;
        leftNode.next = cur;
        return node.next;
    }

    /**
     * 链表中的节点每k个一组翻转
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode pre = node;
        ListNode right = node;
        while (right.next != null) {
            for (int i = 0; i < k && right != null; i++) {
                right = right.next;
            }
            if (right == null) {
                break;
            }

            ListNode left = pre.next;
            ListNode next = right.next;
            right.next = null;
            pre.next = reverse(left);
            left.next = next;
            pre = left;
            right = left;

        }
        return node.next;
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while ( cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }


    /**
     *  合并两个排序的链表
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode node = new ListNode(-1);
        ListNode cur = node;
        while(pHead1 != null && pHead2 != null) {
            if(pHead1.val <= pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;

        }
        cur.next = pHead1 == null ? pHead2 : pHead1;

        return node.next;
    }

    /**
     * 判断链表中是否有环
     */
    public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            // 快指针走两步
            fast = fast.next.next;
            // 慢指针走一步
            slow = slow.next;
            // 相遇则有环
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 链表中环的入口结点
     * @param pHead
     * @return
     */
    public ListNode hasCycle2(ListNode pHead) {
        if(pHead == null) {
            return null;
        }
        //快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        //如果没有环，快指针会先到链表尾
        while(fast != null && fast.next != null) {
            //快指针移动两步
            fast = fast.next.next;
            //慢指针移动一步
            slow = slow.next;
            //相遇则有环
            if(fast == slow) {
                return slow;
            }
        }
        //说明没有环
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle2(pHead);
        if(slow == null) {
            //没有环
            return null;
        }
        //快指针回到链表头
        ListNode fast = pHead;
        //再次相遇即是环入口
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode EntryNodeOfLoop2(ListNode pHead) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode tmp = pHead;
        while(tmp != null) {
            if(set.contains(tmp)) {
                return tmp;
            }
            set.add(tmp);
            tmp = tmp.next;
        }
        return null;

    }

    /**
     * 链表中倒数最后k个结点
     */
    //栈实现
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode tmp = pHead;
        while(tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }
        for(int i = 0; i < k; i++) {
            if(stack.empty()) {
                return null;
            }
            tmp = stack.pop();
        }

        return tmp;
    }
    //快慢指针
    public ListNode FindKthToTail2 (ListNode pHead, int k) {
        // write code here
        int n = 0;
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 快指针先行K步
        for(int i = 0; i < k; i++) {
            if(fast != null) {
                fast = fast.next;
            }else {
                // 达不到K步说明链表过短，没有到数k
                return slow = null;
            }
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    /**
     * 删除链表的倒数第n个节点
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        //添加表头
        ListNode node = new ListNode(-1);
        node.next = head;
        //快满慢节点
        ListNode fast = head;
        ListNode slow = head;
        //慢节点的前置节点
        ListNode pre = node;
        //快指针走n步
        while(n != 0) {
            fast = fast.next;
            n--;
        }
        //快慢指针同步，快指针到底，慢指针就到了第n个位置
        while(fast != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;

        }
        //删除
        pre.next = slow.next;
        return node.next;

    }


    /**
     *  两个链表的第一个公共结点
     */
    //hashSet解法
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        HashSet<ListNode> set = new HashSet<>();
        //先把表1放入hash表中
        ListNode tmp = pHead1;
        while(tmp != null) {
            set.add(tmp);
            tmp = tmp.next;
        }
        //遍历表2
        tmp = pHead2;
        while(tmp != null) {
            if(set.contains(tmp)) {
                break;
            }
            tmp = tmp.next;
        }

        return tmp;
    }

    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while(l1 != l2) {
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;
        }

        return l1;
    }


    //栈
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        ListNode node = null;
        ListNode head = null;
        // 让表1，表2分别入栈
        ListNode tmp = head1;
        while(tmp != null) {
            stack1.push(tmp);
            tmp = tmp.next;
        }
        tmp = head2;
        while(tmp != null) {
            stack2.push(tmp);
            tmp = tmp.next;
        }
        //记录超过9的
        int add = 0;
        while(!stack1.empty() || !stack2.empty() || add != 0) {
            int x = (stack1.isEmpty()) ? 0 : stack1.pop().val;
            int y = (stack2.isEmpty()) ? 0 : stack2.pop().val;
            int sum = x + y + add;
            add = sum / 10;
            node = new ListNode(sum % 10);
            node.next = head;
            head = node;
        }
        return head;
    }

    // 翻转链表
    public ListNode ReverseL(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        ListNode cur = pHead;
        ListNode pre = null;
        while (cur != null) {
            //断开链表，要记录后续一个
            ListNode tmp = cur.next;
            //当前的next指向前一个
            cur.next = pre;
            //前一个更新为当前的
            pre = cur;
            //当前更新为刚刚记录的后一个
            cur = tmp;
        }
        return pre;
    }
    public ListNode addInList2 (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        //反转两个链表
        head1 = ReverseL(head1);
        head2 = ReverseL(head2);
        // 添加表头
        ListNode res = new ListNode(-1);
        ListNode head = res;
        //进位标记
        int add = 0;
        while (head1 != null || head2 != null || add != 0) {
            int x = head1 == null ? 0 : head1.val;
            int y = head2 == null ? 0 : head2.val;
            int sum = x + y + add;
            //更新标志位
            add = sum / 10;
            sum = sum % 10;
            //添加元素
            head.next = new ListNode(sum);
            head = head.next;
            //移动下一个
            if (head1 != null) {
                head1 = head1.next;
            }
            if (head2 != null) {
                head2 = head2.next;
            }
        }

        return ReverseL(res.next);
    }


    /**
     * 单链表的排序
     */
    //归并排序法
    public ListNode merge(ListNode pHead1, ListNode pHead2) {
        //一个已经为空了，直接返回另一个
        if(pHead1 == null) {
            return pHead2;
        }
        if(pHead2 == null) {
            return pHead1;
        }
        //加一个表头
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //两个链表都不要为空
        while(pHead1 != null && pHead2 != null) {
            //取较小值的节点
            if(pHead1.val < pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            //指针后移
            cur = cur.next;
        }
        //最后那个链表不为空，直接接在后面
        if(pHead1 != null) {
            cur.next = pHead1;
        }
        if(pHead2 != null) {
            cur.next = pHead2;
        }
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        //链表为空或者只有一个元素，直接就是有序的
        if(head == null || head.next == null) {
            return  head;
        }
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //右边的指针到达末尾时，中间指针指向该段链表的中间
        while(right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //左边指针指向左段的最后的第一个节点，从这里断开
        left.next = null;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid));

    }
    //转为数组排序
    public ListNode sortInList2 (ListNode head) {
        // write code here
        ArrayList<Integer> nums = new ArrayList<>();
        ListNode p = head;
        // 遍历链表，将节点加入数组
        while(p != null) {
            nums.add(p.val);
            p = p.next;
        }
        p = head;
        //对数组元素排序
        Collections.sort(nums);
        //遍历数组
        for(int i = 0; i < nums.size(); i++) {
            //将数组依次加入链表
            p.val = nums.get(i);
            p = p.next;
        }
        return head;
    }

    /**
     * 判断一个链表是否为回文结构
     */
    //双指针找中点
    public ListNode reverse3 (ListNode head) {
        ListNode pre = null;
        while(head != null ) {
            ListNode cur = head.next;
            head.next = pre;
            pre = head;
            head = cur;
        }
        return pre;
    }
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null) {
            return false;
        }
        // 快慢指针找到中点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //中点出翻转
        slow = reverse3(slow);
        fast = head;
        while(slow != null) {
            if(slow.val != fast.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }

    /**
     * 链表的奇偶重排
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        //如果链表为空，直接返回
        if(head == null || head.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode cur = even;
        while(even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = cur;
        return head;
    }


    /**
     * 删除有序链表中重复的元素-I
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null) {
            return head;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }


    /**
     * 删除有序链表中重复的元素-II
     */
    public ListNode deleteDuplicates2 (ListNode head) {
        // write code here
        if(head == null) {
            return head;
        }
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode cur = node;
        while(cur.next != null && cur.next.next != null) {
            if(cur.next.val == cur.next.next.val) {
                int tmp = cur.next.val;
                while(cur.next != null && cur.next.val == tmp) {
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return node.next;

    }






}
